#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <bits/extc++.h>
using namespace std;

namespace fastio{
    struct{template<typename T>operator T(){
        T x=0;char f=0,c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
        while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
        return f?-x:x;
    }}in;int stk[40],tp;
    template<typename T>void out(T x,char c=0){
        if(x<0)putchar('-'),x=-x;
        do stk[++tp]=x%10,x/=10;while(x);
        while(tp)putchar(stk[tp--]^48);
        if(c)putchar(c);
    }
}using fastio::in;using fastio::out;

const int N = 100005;
int a[N];
int n,K;

namespace sub1{
    const int M = 1005;
    int le[N],ri[N],t[M][M],T[M][M],tag;
    vector<int> q;
    void work(){
        q = {0};
        for(int K=1;K<=n;K++){
            while(a[K]>=a[q.back()])
                q.pop_back();
            le[K] = q.back();
            q.push_back(K);
        }
        q = {n+1};
        for(int K=n;K;K--){
            while(a[K]>=a[q.back()])
                q.pop_back();
            ri[K] = q.back();
            q.push_back(K);
        }
    }

    int dfs(int l,int r){
        if(T[l][r]!=tag){
            t[l][r] = 0;
            T[l][r] = tag;
        }
        if(t[l][r])
            return t[l][r];
        int ans;
        if(l==0&&r==n+1)
            ans = 0;
        else if(a[l]<a[r])
            ans = dfs(le[l],r)+1;
        else if(a[l]>a[r])
            ans = dfs(l,ri[r])+1;
        else
            ans = dfs(le[l],ri[r])+1;
        return t[l][r]=ans;
    }
    int main(){
        a[0] = a[n+1] = 1e9;
        int q = in;
        while(q--){
            tag++;
            int x = in,l = in,r = in;
            swap(a[x],a[x+1]);
            work();
            int ans = 0;
            for(int K=l;K<=r;K++)
                ans += dfs(le[K],ri[K])*K+n-1;
            out(ans,'\n');
        }
        return 0;
    }
}

struct name{
    int x,l,r;
}qu[N];
int q;
namespace sub_wg{
    __gnu_pbds::cc_hash_table<int,int> t;
    int l[N][2],r[N][2],z[N],top,w[N][2],cf[N][2],sum[N][2];
    void work(int K){
        t.clear();
        for(int k=1;k<=n;k++){
            if(t[a[k]]){
                cf[t[a[k]]][K]++;
                cf[k+1][K]--;
            }
            else
                t[a[k]] = k;
        }
        for(int k=1;k<=n;k++)
            sum[k][K] = sum[k-1][K]+cf[k][K];
        top = 0;
        for(int k=1;k<=n;k++){
            while(top&&a[k]>=z[top])
                top--;
            l[k][K] = top;
            z[++top] =a[k];
        }
        top = 0;
        for(int k=n;k;k--){
            while(top&&a[k]>=z[top])
                top--;
            r[k][K] = top;
            z[++top] = a[k];
        }
    }
    int main(){
        work(0);
        swap(a[qu[1].x],a[qu[1].x+1]);
        work(1);
        for(int k=1;k<=n;k++)
            for(int K=0;K<=1;K++)
                l[k][K]+=l[k-1][K];
        for(int k=n;k;k--)
            for(int K=0;K<=1;K++)
                r[k][K]+=r[k+1][K];
        for(int k=1;k<=q;k++)
            out((l[qu[k].r][k&1]-l[qu[k].l-1][k&1]+r[qu[k].l][k&1]-r[qu[k].r+1][k&1]-sum[qu[k].r][k&1]-sum[qu[k].l-1][k&1])*K+(qu[k].r-qu[k].l+1)*(n-1),'\n');
        return 0;
    }
}

int main(){
    freopen("summer.in","r",stdin);
    freopen("summer.out","w",stdout);
    n = in,K = in;
    for(int K=1;K<=n;K++)
        a[K] = in;
    if(n<=1000)
        return sub1::main();
    q = in;
    for(int k=1;k<=q;k++)
        qu[k].x=in,qu[k].l=in,qu[k].r=in;
    sub_wg::main();
    return 0;
}